class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # 如果列表为空
        if nums == []:
            return 0
        # 如果列表长度小于2，求两个的最大值即可
        if len(nums) <= 2:
            return max(nums)
        dp = [0]*len(nums)
        dp[0] = nums[0]
        dp[1] = max(nums[1], nums[0])
        for i in range(2, len(nums)):
            dp[i] = max(dp[i-1], dp[i-2]+nums[i])
        return dp[len(nums)-1]


if __name__ == '__main__':
    s = Solution()
    n = [2, 7, 9, 3, 1]
    print(s.rob(n))
